<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            常见的排序算法总结 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">常见的排序算法总结</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2018-12-11 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E6%8E%92%E5%BA%8F/">排序</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>5.2k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>25 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <h2 id="常见排序算法总结"><a href="#常见排序算法总结" class="headerlink" title="常见排序算法总结"></a>常见排序算法总结</h2><p>关于排序的部分一直想总结下一直没时间，现在来总结下吧。gif图来自微信上的文章 (<strong>五分钟学算法</strong>的公众号，挺不错干货挺多的)，原理性的东西就不讲了，图讲的比我好。如果还是不懂可以看看《算法》里面的轨迹图，那个也很直观 </p>
<h3 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h3><p>  <img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/f02ace7b7fb9b810274e683c2be54a02_640_wx_fmt=gif&tp=webp&wxfrom=5&wx_lazy=1.gif"
                      alt="weixin"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//冒泡排序</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">MaoPaoSort</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=nums.length-<span class="number">1</span>;i&gt;=<span class="number">0</span>;i--)&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;i;j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(nums[j]&gt;nums[j+<span class="number">1</span>])&#123;</span><br><span class="line">                swap(nums,j,j+<span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h3><p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/640.gif"
                      alt="weixin"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//选择排序</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">SelectSort</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++)&#123;</span><br><span class="line">        <span class="keyword">int</span> min=nums[i];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=i+<span class="number">1</span>;j&lt;nums.length;j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(nums[j]&lt;min)&#123;</span><br><span class="line">                min=nums[j];</span><br><span class="line">                swap(nums,j,i);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="直接插入排序"><a href="#直接插入排序" class="headerlink" title="直接插入排序"></a>直接插入排序</h3><p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/640%20%281%29.gif"
                      alt="weixin"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//直接插入排序</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">InsertSort</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;nums.length;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=i;j&gt;<span class="number">0</span>&amp;&amp;nums[j]&lt;nums[j-<span class="number">1</span>];j--)&#123;</span><br><span class="line">            swap(nums,j,j-<span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h3><p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/640%20%282%29.gif"
                      alt="weixin"
                ></p>
<h4 id="图上面的是递归版本的归并，实现如下"><a href="#图上面的是递归版本的归并，实现如下" class="headerlink" title="图上面的是递归版本的归并，实现如下"></a>图上面的是递归版本的归并，实现如下</h4><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//归并排序</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">MergerSort</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">    help=<span class="keyword">new</span> <span class="keyword">int</span>[nums.length];</span><br><span class="line">    MergerSort(nums,<span class="number">0</span>,nums.length-<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">MergerSort</span><span class="params">(<span class="keyword">int</span> []nums,<span class="keyword">int</span> left,<span class="keyword">int</span> right)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(left&gt;=right)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//不能直接在这里创建数组，严重影响性能，可以在上面再套一层方法，或者采用merger2的方式(也不好，应该保证辅助数组只初始化一次)</span></span><br><span class="line">    <span class="comment">//help=new int[nums.length];</span></span><br><span class="line">    <span class="keyword">int</span> mid=left+((right-left)&gt;&gt;<span class="number">1</span>);</span><br><span class="line">    MergerSort(nums,left,mid);</span><br><span class="line">    MergerSort(nums,mid+<span class="number">1</span>,right);</span><br><span class="line">    merger(nums,left,mid,right);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//辅助数组</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">int</span> []help;</span><br><span class="line"></span><br><span class="line"><span class="comment">//归并操作</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">merger</span><span class="params">(<span class="keyword">int</span> []nums ,<span class="keyword">int</span> left,<span class="keyword">int</span> mid,<span class="keyword">int</span> right)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i=left,j=mid+<span class="number">1</span>;</span><br><span class="line">    <span class="comment">//其实没区别空间复杂度，都是O(N) 后面这个会更加耗费时间</span></span><br><span class="line">    <span class="comment">//int []help=new int[right-left+1];</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> k=left;k&lt;=right;k++)&#123;</span><br><span class="line">        <span class="comment">//一边的到达尽头,先判断两个边界,不然就要想下面那样写</span></span><br><span class="line">        <span class="keyword">if</span>(i&gt;mid)&#123;</span><br><span class="line">            help[k]=nums[j++];</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span>(j&gt;right)&#123;</span><br><span class="line">            help[k]=nums[i++];</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span>(nums[i]&gt;nums[j])&#123;</span><br><span class="line">            help[k]=nums[j++];</span><br><span class="line">        &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="comment">//相等的时候左边先进栈保证稳定性</span></span><br><span class="line">            help[k]=nums[i++];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">/*// 2 </span></span><br><span class="line"><span class="comment">            if( i&lt;=mid &amp;&amp;j&lt;=right &amp;&amp; nums[i]&gt;nums[j])&#123;</span></span><br><span class="line"><span class="comment">                help[k]=nums[j++];</span></span><br><span class="line"><span class="comment">            &#125;else if( i&lt;=mid &amp;&amp;j&lt;=right &amp;&amp; nums[i]&lt;=nums[j])&#123;</span></span><br><span class="line"><span class="comment">                //相等的时候左边先进栈保证稳定性</span></span><br><span class="line"><span class="comment">                help[k]=nums[i++];</span></span><br><span class="line"><span class="comment">            &#125;else if(i&gt;mid)&#123;</span></span><br><span class="line"><span class="comment">                help[k]=nums[j++];</span></span><br><span class="line"><span class="comment">            &#125;else if(j&gt;right)&#123; </span></span><br><span class="line"><span class="comment">                help[k]=nums[i++];</span></span><br><span class="line"><span class="comment">            &#125;*/</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//复制</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> k=left;k&lt;=right;k++)&#123;</span><br><span class="line">        nums[k]=help[k];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*while (p1 &lt;= m &amp;&amp; p2 &lt;= r) &#123;</span></span><br><span class="line"><span class="comment">            help[i++] = arr[p1] &lt; arr[p2] ? arr[p1++] : arr[p2++];</span></span><br><span class="line"><span class="comment">        &#125;</span></span><br><span class="line"><span class="comment">        while (p1 &lt;= m) &#123;</span></span><br><span class="line"><span class="comment">            help[i++] = arr[p1++];</span></span><br><span class="line"><span class="comment">        &#125;</span></span><br><span class="line"><span class="comment">        while (p2 &lt;= r) &#123;</span></span><br><span class="line"><span class="comment">            help[i++] = arr[p2++];</span></span><br><span class="line"><span class="comment">        &#125;</span></span><br><span class="line"><span class="comment">        for (i = 0; i &lt; help.length; i++) &#123;</span></span><br><span class="line"><span class="comment">            arr[l + i] = help[i];</span></span><br><span class="line"><span class="comment">        &#125;*/</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="非递归版本"><a href="#非递归版本" class="headerlink" title="非递归版本"></a>非递归版本</h4><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//归并排序（非递归，方向不一样，时间复杂度一样都为O(NlogN)</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">MergerSortNoRecurse</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">    help=<span class="keyword">new</span> <span class="keyword">int</span>[nums.length];</span><br><span class="line">    <span class="comment">//控制合并的长度 </span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> sz=<span class="number">1</span>;sz&lt;nums.length;sz*=<span class="number">2</span>)&#123;</span><br><span class="line">        <span class="comment">//控制合并的向后移动</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length-sz;i+=<span class="number">2</span>*sz)&#123;</span><br><span class="line">            <span class="keyword">int</span> r=i+<span class="number">2</span>*sz-<span class="number">1</span>&lt;nums.length-<span class="number">1</span>?i+<span class="number">2</span>*sz-<span class="number">1</span>:nums.length-<span class="number">1</span>;</span><br><span class="line">            merger(nums,i,i+sz-<span class="number">1</span>,r);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="三向切分的快排-荷兰国旗问题"><a href="#三向切分的快排-荷兰国旗问题" class="headerlink" title="三向切分的快排(荷兰国旗问题)"></a>三向切分的快排(荷兰国旗问题)</h3><p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/640%20%283%29.gif"
                      alt="weixin"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//快排 (不具有稳定性或者难以实现)</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">QuickSort</span><span class="params">(<span class="keyword">int</span> []nums,<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(l&gt;r)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//随机一个数和r交换 ---随机快排</span></span><br><span class="line">    swap(nums, l + (<span class="keyword">int</span>) (Math.random() * (r - l + <span class="number">1</span>)), r);</span><br><span class="line">    <span class="keyword">int</span> []index=partition2(nums,l,r);</span><br><span class="line">    QuickSort(nums,l,index[<span class="number">0</span>]-<span class="number">1</span>);</span><br><span class="line">    QuickSort(nums,index[<span class="number">1</span>]+<span class="number">1</span>,r);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">partition1</span><span class="params">(<span class="keyword">int</span> []nums ,<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> base = l;</span><br><span class="line">    <span class="comment">//双指针</span></span><br><span class="line">    <span class="keyword">int</span> lo = l, hi = r;</span><br><span class="line">    <span class="comment">//这种partition的实现细节有点不好理解</span></span><br><span class="line">    <span class="comment">//这种partition不能随机基准元素。。。。</span></span><br><span class="line">    <span class="comment">//参照了左神的代码发现其实可以在partition之前随机一个变量和lo交换，也有同样的效果也消除了输入的影响</span></span><br><span class="line">    <span class="keyword">while</span> (lo &lt; hi) &#123;</span><br><span class="line">        <span class="comment">//必须先从右往左,主要是为了归位的时候不出现问题</span></span><br><span class="line">        <span class="comment">//比如这里选取的基准元素是 lo 也就是子数组的第一个元素，如果先从左往右最后交换的就是lo和一个比lo大的数然而比lo大的数应该放在右边</span></span><br><span class="line">        <span class="comment">//反之如果选的是hi为基准就要先从左往右</span></span><br><span class="line">        <span class="comment">// 7  0  1  2    10  11  22</span></span><br><span class="line">        <span class="keyword">while</span> (nums[hi] &gt;= nums[base] &amp;&amp; lo &lt; hi) &#123;</span><br><span class="line">            hi--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span> (nums[lo] &lt;= nums[base] &amp;&amp; lo &lt; hi) &#123;</span><br><span class="line">            lo++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (lo &lt; hi) &#123;</span><br><span class="line">            swap(nums, lo, hi);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//归位 lo==hi</span></span><br><span class="line">    swap(nums, hi, base);</span><br><span class="line">    <span class="keyword">return</span> lo;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//荷兰国旗优化的快排</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span>[] partition2(<span class="keyword">int</span> []arr ,<span class="keyword">int</span> l,<span class="keyword">int</span> r)&#123;</span><br><span class="line">    <span class="comment">// 7  0  1  2    10  11  22        </span></span><br><span class="line">    <span class="comment">//小于区为空</span></span><br><span class="line">    <span class="keyword">int</span> less=l-<span class="number">1</span>;</span><br><span class="line">    <span class="comment">//l ----&gt; more 为待定区</span></span><br><span class="line">    <span class="keyword">int</span> more=r;</span><br><span class="line">    <span class="keyword">while</span>(l&lt;more)&#123;</span><br><span class="line">        <span class="keyword">if</span>(arr[l]&lt;arr[r])&#123;</span><br><span class="line">            swap(arr,++less,l++);</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span>(arr[l]&gt;arr[r])&#123;</span><br><span class="line">            <span class="comment">//大于基准时 , 大于区扩大(大于区的前一个元素和当前元素交换，但是不知道大于区的前一个元素是什么情况，所以不能l++)</span></span><br><span class="line">            swap(arr,--more,l);</span><br><span class="line">        &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">            l++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//和大于区间的第一个交换 保证归位正确,如果选取的是以最左边为基准元素 这里就应该和less交换</span></span><br><span class="line">    <span class="comment">//到这里  [less+1,more-1]之间都是等于 基准元素 arr【r】 的</span></span><br><span class="line">    swap(arr,more,r);</span><br><span class="line">    <span class="comment">//到这  [less+1,more]之间都是等于 基准元素 arr【r】 的</span></span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;less+<span class="number">1</span>,more&#125;;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h3><p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/640%20%284%29.gif"
                      alt="weixin"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//堆排序</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">HeapSort</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(nums.length&lt;<span class="number">2</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//构建大根堆</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>; i&lt;nums.length; i++) &#123;</span><br><span class="line">        heapInsert(nums,i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//交换堆顶和最后一个节点</span></span><br><span class="line">    <span class="keyword">int</span> size= nums.length;</span><br><span class="line">    swap(nums,size-<span class="number">1</span>,<span class="number">0</span>);</span><br><span class="line">    size--;</span><br><span class="line">    <span class="keyword">while</span>(size&gt;<span class="number">1</span>)&#123;</span><br><span class="line">        <span class="comment">//调整</span></span><br><span class="line">        heapIfy(nums,<span class="number">0</span>,size);</span><br><span class="line">        <span class="comment">//每次都和最后一个孩子节点交换，然后size--</span></span><br><span class="line">        swap(nums,--size,<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//向上爬</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">heapInsert</span><span class="params">(<span class="keyword">int</span> []nums, <span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">    <span class="comment">//迭代比较当前节点和父节点的值的大小</span></span><br><span class="line">    <span class="keyword">while</span>(nums[index]&gt;nums[(index-<span class="number">1</span>)/<span class="number">2</span>])&#123;</span><br><span class="line">        swap(nums,index,(index-<span class="number">1</span>)/<span class="number">2</span>);</span><br><span class="line">        index=(index-<span class="number">1</span>)/<span class="number">2</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//向下爬</span></span><br><span class="line"><span class="comment">//index位置的值变小后继续调整为大根堆</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">heapIfy</span><span class="params">(<span class="keyword">int</span> []nums,<span class="keyword">int</span> index,<span class="keyword">int</span> size)</span></span>&#123;</span><br><span class="line">    <span class="comment">//左孩子</span></span><br><span class="line">    <span class="keyword">int</span> left=index*<span class="number">2</span>+<span class="number">1</span>;</span><br><span class="line">    <span class="comment">//节点有左孩子</span></span><br><span class="line">    <span class="keyword">while</span>(left&lt;size)&#123;</span><br><span class="line">        <span class="comment">//判断是否有右孩子.....</span></span><br><span class="line">        <span class="comment">//左右孩子里的最大值 有右孩子且右孩子大于左孩子</span></span><br><span class="line">        <span class="keyword">int</span> largest=left+<span class="number">1</span>&lt;size &amp;&amp; nums[left]&lt;nums[left+<span class="number">1</span>] ?left+<span class="number">1</span>:left;</span><br><span class="line">        largest=nums[largest]&gt;nums[index]?largest:index;</span><br><span class="line">        <span class="comment">//最大值等于自己</span></span><br><span class="line">        <span class="keyword">if</span>(largest==index)&#123;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//交换大孩子节点和自己</span></span><br><span class="line">        swap(nums,largest,index);</span><br><span class="line">        <span class="comment">//设置大孩子的index和左孩子</span></span><br><span class="line">        index=largest;</span><br><span class="line">        left=index*<span class="number">2</span>+<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="堆排序更优的做法"><a href="#堆排序更优的做法" class="headerlink" title="堆排序更优的做法"></a>堆排序更优的做法</h3><p>上面的做法并不是最优的堆排序</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">heapSort</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> last=nums.length-<span class="number">1</span>;</span><br><span class="line">    <span class="comment">//N构建大根堆</span></span><br><span class="line">    <span class="comment">//从倒数第二层开始</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=nums.length/<span class="number">2</span>-<span class="number">1</span> ;i&gt;=<span class="number">0</span>;i--)&#123;</span><br><span class="line">        heapIfy(nums,i,last);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//printArray(nums);</span></span><br><span class="line">    <span class="keyword">while</span>(last&gt;=<span class="number">1</span>)&#123;</span><br><span class="line">        swap(nums,<span class="number">0</span>,last--);</span><br><span class="line">        heapIfy(nums,<span class="number">0</span>,last);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//i 大根堆调整</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">heapIfy</span><span class="params">(<span class="keyword">int</span>[] nums,<span class="keyword">int</span> i,<span class="keyword">int</span> last)</span></span>&#123;</span><br><span class="line">    <span class="comment">//判断有没有子节点（左孩子）</span></span><br><span class="line">    <span class="keyword">int</span> left=i*<span class="number">2</span>+<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(left&lt;=last)&#123;</span><br><span class="line">        <span class="keyword">int</span> right=left+<span class="number">1</span>;</span><br><span class="line">        <span class="comment">//左右节点最大值</span></span><br><span class="line">        <span class="keyword">int</span> larger=right&lt;=last &amp;&amp; nums[right] &gt; nums[left]?right:left;</span><br><span class="line">        <span class="keyword">if</span>(nums[larger]&gt;nums[i])&#123;</span><br><span class="line">            swap(nums,larger,i);</span><br><span class="line">            i=larger;</span><br><span class="line">            left=larger*<span class="number">2</span>+<span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span>  <span class="keyword">void</span>  <span class="title">swap</span><span class="params">(<span class="keyword">int</span> []nums,<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> temp=nums[a];</span><br><span class="line">    nums[a]=nums[b];</span><br><span class="line">    nums[b]=temp;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>对比之前的方法，构造堆的方式发生了变化，上面那种通过自上而下的<code>insert</code>方式时间复杂度是<code>O(NlogN)</code>，其实仔细想想，这两种方式是完全相反的，insert的方式，最后一层每个元素最坏都可能调整<code>logN</code>次，而最后一层也是元素最多的一层，这样一来复杂度就会大大增加，相反如果采用从底向上的<code>heapIfy</code>方式最后一层都只需要调整<code>1</code>次，而根节点需要调整<code>logN</code>次，而根节点<strong>只有一个</strong>时间复杂度就会大大降低，最终的时间复杂度就是O(N)，<a class="link"   target="_blank" rel="noopener" href="https://www.zhihu.com/question/20729324" >具体推算过程可以看这些回答<i class="fas fa-external-link-alt"></i></a> </p>
<p><strong>手推过程</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/image/20190617/kVuvnMfjuSns.png?imageslim"
                      alt="img"
                ></p>
<p>最后推得到得复杂度是小于<code>O(2N)</code>，也就是<code>O(N)</code>的时间复杂度，如果不是刷<code>leetCode</code> 看到了类似的题可能会一直被那样去写😂</p>
<p><strong>再回首</strong></p>
<p>时隔多年，又回头写了一个，写了大概半个小时左右，边写边回忆，感觉这个写法比上面好一点点，所以记录一下</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">import</span> java.io.*;</span><br><span class="line"><span class="keyword">import</span> java.util.*;</span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Main</span></span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span></span>&#123;</span><br><span class="line">        Scanner sc=<span class="keyword">new</span> Scanner(System.in);</span><br><span class="line">        <span class="keyword">int</span> N=sc.nextInt();</span><br><span class="line">        <span class="keyword">int</span>[] nums=<span class="keyword">new</span> <span class="keyword">int</span>[N];</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;N;i++)nums[i]=sc.nextInt();</span><br><span class="line">        heapSort(nums);</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;N;i++)System.out.print(nums[i]+<span class="string">&quot; &quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">heapSort</span><span class="params">(<span class="keyword">int</span>[] nums)</span></span>&#123;</span><br><span class="line">        <span class="comment">//求左右孩子</span></span><br><span class="line">        <span class="comment">//       0 </span></span><br><span class="line">        <span class="comment">//   1       2</span></span><br><span class="line">        <span class="comment">// 3   4   5   6 </span></span><br><span class="line">        <span class="comment">//7                 7/2=3  4/2=1 8/2=4</span></span><br><span class="line">        <span class="comment">//O(N)构建堆</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=nums.length/<span class="number">2</span>;i&gt;=<span class="number">0</span>;i--)&#123; <span class="comment">//从2/n开始down构建二叉树,不一定要精确,多一两个无所谓</span></span><br><span class="line">            down(nums,i,nums.length);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> index=<span class="number">0</span>,tail=nums.length;</span><br><span class="line">        <span class="comment">//堆排,将堆头放到尾部</span></span><br><span class="line">        <span class="keyword">while</span>(tail&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            swap(nums,index,--tail);</span><br><span class="line">            down(nums,index,tail);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">down</span><span class="params">(<span class="keyword">int</span>[] nums,<span class="keyword">int</span> index,<span class="keyword">int</span> size)</span></span>&#123;</span><br><span class="line">        <span class="comment">//求左右孩子</span></span><br><span class="line">        <span class="comment">//      0 </span></span><br><span class="line">        <span class="comment">//  1       2</span></span><br><span class="line">        <span class="comment">//3   4   5   6</span></span><br><span class="line">        <span class="keyword">while</span>(index*<span class="number">2</span>+<span class="number">1</span> &lt; size)&#123; <span class="comment">//还有孩子</span></span><br><span class="line">            <span class="keyword">int</span> left=index*<span class="number">2</span>+<span class="number">1</span>,right=left+<span class="number">1</span>;</span><br><span class="line">            <span class="comment">//左右子树中的较大</span></span><br><span class="line">            <span class="keyword">int</span> largeIndex = right&lt;size &amp;&amp; nums[left]&lt;nums[right] ? right:left;</span><br><span class="line">            <span class="keyword">if</span>(nums[index] &gt;= nums[largeIndex])&#123;</span><br><span class="line">                <span class="keyword">return</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            swap(nums,index,largeIndex);</span><br><span class="line">            index=largeIndex;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">swap</span><span class="params">(<span class="keyword">int</span>[] nums,<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> temp=nums[a];</span><br><span class="line">        nums[a]=nums[b];</span><br><span class="line">        nums[b]=temp;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h3 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h3><p>实际上写排序就是基于插入排序的，在它之上进行了数学上的优化。</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/640%20%285%29.gif"
                      alt="image"
                ><br>    实际上从逆序对的角度来看，基于比较的排序就是为了消除逆序对的个数，而诸如冒泡选择每次都只是交换相邻的两个元素，每次交换最多只减少一个逆序对，而希尔排序扩大了这个间距，就增大了减少逆序对的可能。不过要研究他的时间复杂度就是数学上的研究的问题了，至于每次间距都减半这个也是根据大样本测试下这种递增序列性能会更好 O(∩_∩)O</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//插入排序的改进</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">ShellSort</span><span class="params">(<span class="keyword">int</span> [] nums)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> h=nums.length&gt;&gt;<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(h&gt;<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=h;i&lt;nums.length;i++)&#123;</span><br><span class="line">            <span class="comment">//实际上是增大了插入排序的间隙，最后还是对进行一次插入排序,不过那个时候的数据已经是高度有序了</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j=i;j-h&gt;=<span class="number">0</span>&amp;&amp;nums[j]&lt;nums[j-h];j-=h) &#123;</span><br><span class="line">                swap(nums,j,j-h);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        h=h&gt;&gt;<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<hr>
<h3 id="BUG"><a href="#BUG" class="headerlink" title="BUG"></a>BUG</h3><p>排个序还能排出Bug？对的没错就是排出了Bug🤣 看看我最开始写的交换函数</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">swap</span><span class="params">(<span class="keyword">int</span> []nums,<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">    nums[a]=nums[a]^nums[b];</span><br><span class="line">    nums[b]=nums[a]^nums[b];</span><br><span class="line">    nums[a]=nums[a]^nums[b];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>为了抖这个机灵付出了惨痛的代价，之前用 &gt;&gt; 拿来当除2操作的时候就忽略了<code>优先级</code>的问题。。。那这里的机灵有什么问题呢？一个数异或同一个数两次就还原没毛病啊？But如果交换的两个数是同一个元素比如上面在数组中 a==b时 nums[a]异或了3次自己相当于<code>nums[a]^nums[a]^nums[a]^nums[a]=0^0=0</code>，最后就会出问题,其实开始前面的排序都没有出现问题，主要是后面的快排时发现了这个Bug因为快排为了避免数据分布的影响随机选取基准值，可能随机的是最后一个，而且快排的partition过程中也会有时也会自己和自己交换，最开始的第一步就是自己和直接交换，让小于区扩大。所以这个方法仅仅只能用来抖一抖机灵，没啥实际意义，以后还是要老老实实写，不然咋死的都不知道😁</p>
<blockquote>
<p> 未完待续……还有一类非基于比较的排序 桶排序之类的等后面再来总结加上去.</p>
</blockquote>
<h3 id="对数器"><a href="#对数器" class="headerlink" title="对数器"></a>对数器</h3><p>直接拿的左神的对数器😄，所有排序都是经过对数器测试的。 <em>talk is cheap show me the code</em></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"><span class="keyword">import</span> java.util.Random;</span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Sorts</span></span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        <span class="comment">/*int []nums=&#123;1,0,-1,-22,213,4,535,-112,99999&#125;;</span></span><br><span class="line"><span class="comment">        //ShellSort(nums);</span></span><br><span class="line"><span class="comment">        //MaoPaoSort(nums);</span></span><br><span class="line"><span class="comment">        //SelectSort(nums);</span></span><br><span class="line"><span class="comment">        //MergerSort(nums,0,nums.length-1);</span></span><br><span class="line"><span class="comment">        QuickSort(nums,0,nums.length-1);</span></span><br><span class="line"><span class="comment">        printArray(nums);*/</span></span><br><span class="line">        <span class="keyword">int</span> testTime = <span class="number">10000</span>;</span><br><span class="line">        <span class="keyword">int</span> maxSize = <span class="number">10000</span>;</span><br><span class="line">        <span class="keyword">int</span> maxValue = <span class="number">100</span>;</span><br><span class="line">        Boolean succeed = <span class="keyword">true</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; testTime; i++) &#123;</span><br><span class="line">            <span class="keyword">int</span>[] arr1 = generateRandomArray(maxSize, maxValue);</span><br><span class="line">            <span class="keyword">int</span>[] arr2 = copyArray(arr1);</span><br><span class="line">            <span class="keyword">long</span> time=System.currentTimeMillis();</span><br><span class="line">            <span class="comment">//冒泡</span></span><br><span class="line">            <span class="comment">//MaoPaoSort(arr1);</span></span><br><span class="line">            <span class="comment">//选择</span></span><br><span class="line">            <span class="comment">//SelectSort(arr1);</span></span><br><span class="line">            <span class="comment">//插入</span></span><br><span class="line">            <span class="comment">//InsertSort(arr1);</span></span><br><span class="line">            <span class="comment">//归并</span></span><br><span class="line">            <span class="comment">//MergerSort(arr1);</span></span><br><span class="line">            <span class="comment">//非递归归并</span></span><br><span class="line">            <span class="comment">//MergerSortNoRecurse(arr1);</span></span><br><span class="line">            <span class="comment">//希尔</span></span><br><span class="line">            <span class="comment">//ShellSort(arr1);</span></span><br><span class="line">            <span class="comment">//快排</span></span><br><span class="line">            <span class="comment">//QuickSort(arr1,0,arr1.length-1);</span></span><br><span class="line">            <span class="comment">//堆排序</span></span><br><span class="line">            HeapSort(arr1);</span><br><span class="line">            <span class="keyword">long</span> time2=System.currentTimeMillis();</span><br><span class="line">            <span class="keyword">if</span>(i==<span class="number">0</span>)&#123;</span><br><span class="line">                System.out.println(time2-time);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//系统排序</span></span><br><span class="line">            comparator(arr2);</span><br><span class="line">            <span class="keyword">if</span>(i==<span class="number">0</span>)&#123;</span><br><span class="line">                System.out.println(System.currentTimeMillis()-time2);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (!isEqual(arr1, arr2)) &#123;</span><br><span class="line">                succeed = <span class="keyword">false</span>;</span><br><span class="line">                printArray(arr1);</span><br><span class="line">                printArray(arr2);</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(succeed ? <span class="string">&quot;Nice!&quot;</span> : <span class="string">&quot;Fucking fucked!&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//初级排序算法</span></span><br><span class="line">    <span class="comment">//************************************************************************</span></span><br><span class="line">    <span class="comment">//冒泡排序</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">MaoPaoSort</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=nums.length-<span class="number">1</span>;i&gt;=<span class="number">0</span>;i--)&#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;i;j++)&#123;</span><br><span class="line">                <span class="keyword">if</span>(nums[j]&gt;nums[j+<span class="number">1</span>])&#123;</span><br><span class="line">                    swap(nums,j,j+<span class="number">1</span>);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//************************************************************************</span></span><br><span class="line">    <span class="comment">//选择排序</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">SelectSort</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++)&#123;</span><br><span class="line">            <span class="keyword">int</span> min=nums[i];</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j=i+<span class="number">1</span>;j&lt;nums.length;j++)&#123;</span><br><span class="line">                <span class="keyword">if</span>(nums[j]&lt;min)&#123;</span><br><span class="line">                    min=nums[j];</span><br><span class="line">                    swap(nums,j,i);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//************************************************************************</span></span><br><span class="line">    <span class="comment">//直接插入排序</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">InsertSort</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;nums.length;i++)&#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j=i;j&gt;<span class="number">0</span>&amp;&amp;nums[j]&lt;nums[j-<span class="number">1</span>];j--)&#123;</span><br><span class="line">                swap(nums,j,j-<span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//************************************************************************</span></span><br><span class="line">    <span class="comment">//插入排序的改进</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">ShellSort</span><span class="params">(<span class="keyword">int</span> [] nums)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> h=nums.length&gt;&gt;<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span>(h&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i=h;i&lt;nums.length;i++)&#123;</span><br><span class="line">                <span class="comment">//实际上是增大了插入排序的间隙，最后还是对进行一次插入排序,不过那个时候的数据已经是高度有序了</span></span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> j=i;j-h&gt;=<span class="number">0</span>&amp;&amp;nums[j]&lt;nums[j-h];j-=h) &#123;</span><br><span class="line">                    swap(nums,j,j-h);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            h=h&gt;&gt;<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//************************************************************************</span></span><br><span class="line">    <span class="comment">//归并排序</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">MergerSort</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">        help=<span class="keyword">new</span> <span class="keyword">int</span>[nums.length];</span><br><span class="line">        MergerSort(nums,<span class="number">0</span>,nums.length-<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">MergerSort</span><span class="params">(<span class="keyword">int</span> []nums,<span class="keyword">int</span> left,<span class="keyword">int</span> right)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(left&gt;=right)&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//不能直接在这里创建数组，严重影响性能，可以在上面再套一层方法，或者采用merger2的方式(也不好，应该保证辅助数组只初始化一次)</span></span><br><span class="line">        <span class="comment">//help=new int[nums.length];</span></span><br><span class="line">        <span class="keyword">int</span> mid=left+((right-left)&gt;&gt;<span class="number">1</span>);</span><br><span class="line">        MergerSort(nums,left,mid);</span><br><span class="line">        MergerSort(nums,mid+<span class="number">1</span>,right);</span><br><span class="line">        merger(nums,left,mid,right);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//辅助数组</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">int</span> []help;</span><br><span class="line">    <span class="comment">//归并操作</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">merger</span><span class="params">(<span class="keyword">int</span> []nums ,<span class="keyword">int</span> left,<span class="keyword">int</span> mid,<span class="keyword">int</span> right)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> i=left,j=mid+<span class="number">1</span>;</span><br><span class="line">        <span class="comment">//其实没区别空间复杂度，都是O(N) 后面这个会更加耗费时间</span></span><br><span class="line">        <span class="comment">//int []help=new int[right-left+1];</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> k=left;k&lt;=right;k++)&#123;</span><br><span class="line">            <span class="comment">//一边的到达尽头,先判断两个边界,不然就要想下面那样写</span></span><br><span class="line">            <span class="keyword">if</span>(i&gt;mid)&#123;</span><br><span class="line">                help[k]=nums[j++];</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span>(j&gt;right)&#123;</span><br><span class="line">                help[k]=nums[i++];</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span>(nums[i]&gt;nums[j])&#123;</span><br><span class="line">                help[k]=nums[j++];</span><br><span class="line">            &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">                <span class="comment">//相等的时候左边先进栈保证稳定性</span></span><br><span class="line">                help[k]=nums[i++];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">/*// 2 </span></span><br><span class="line"><span class="comment">            if( i&lt;=mid &amp;&amp;j&lt;=right &amp;&amp; nums[i]&gt;nums[j])&#123;</span></span><br><span class="line"><span class="comment">                help[k]=nums[j++];</span></span><br><span class="line"><span class="comment">            &#125;else if( i&lt;=mid &amp;&amp;j&lt;=right &amp;&amp; nums[i]&lt;=nums[j])&#123;</span></span><br><span class="line"><span class="comment">                //相等的时候左边先进栈保证稳定性</span></span><br><span class="line"><span class="comment">                help[k]=nums[i++];</span></span><br><span class="line"><span class="comment">            &#125;else if(i&gt;mid)&#123;</span></span><br><span class="line"><span class="comment">                help[k]=nums[j++];</span></span><br><span class="line"><span class="comment">            &#125;else if(j&gt;right)&#123; </span></span><br><span class="line"><span class="comment">                help[k]=nums[i++];</span></span><br><span class="line"><span class="comment">            &#125;*/</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//复制</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> k=left;k&lt;=right;k++)&#123;</span><br><span class="line">            nums[k]=help[k];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//asddsdasdasdasd</span></span><br><span class="line">        <span class="comment">/*while (p1 &lt;= m &amp;&amp; p2 &lt;= r) &#123;</span></span><br><span class="line"><span class="comment">            help[i++] = arr[p1] &lt; arr[p2] ? arr[p1++] : arr[p2++];</span></span><br><span class="line"><span class="comment">        &#125;</span></span><br><span class="line"><span class="comment">        while (p1 &lt;= m) &#123;</span></span><br><span class="line"><span class="comment">            help[i++] = arr[p1++];</span></span><br><span class="line"><span class="comment">        &#125;</span></span><br><span class="line"><span class="comment">        while (p2 &lt;= r) &#123;</span></span><br><span class="line"><span class="comment">            help[i++] = arr[p2++];</span></span><br><span class="line"><span class="comment">        &#125;</span></span><br><span class="line"><span class="comment">        for (i = 0; i &lt; help.length; i++) &#123;</span></span><br><span class="line"><span class="comment">            arr[l + i] = help[i];</span></span><br><span class="line"><span class="comment">        &#125;*/</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//归并排序（非递归，方向不一样，时间复杂度一样都为O(NlogN)</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">MergerSortNoRecurse</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">        help=<span class="keyword">new</span> <span class="keyword">int</span>[nums.length];</span><br><span class="line">        <span class="comment">//控制合并的长度 </span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> sz=<span class="number">1</span>;sz&lt;nums.length;sz*=<span class="number">2</span>)&#123;</span><br><span class="line">            <span class="comment">//控制合并的向后移动</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length-sz;i+=<span class="number">2</span>*sz)&#123;</span><br><span class="line">                <span class="keyword">int</span> r=i+<span class="number">2</span>*sz-<span class="number">1</span>&lt;nums.length-<span class="number">1</span>?i+<span class="number">2</span>*sz-<span class="number">1</span>:nums.length-<span class="number">1</span>;</span><br><span class="line">                merger(nums,i,i+sz-<span class="number">1</span>,r);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//************************************************************************</span></span><br><span class="line">    <span class="comment">//快排 (不具有稳定性或者难以实现)</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">QuickSort</span><span class="params">(<span class="keyword">int</span> []nums,<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(l&gt;r)&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//随机一个数和r交换 ---随机快排</span></span><br><span class="line">        swap(nums, l + (<span class="keyword">int</span>) (Math.random() * (r - l + <span class="number">1</span>)), r);</span><br><span class="line">        <span class="keyword">int</span> []index=partition2(nums,l,r);</span><br><span class="line">        QuickSort(nums,l,index[<span class="number">0</span>]-<span class="number">1</span>);</span><br><span class="line">        QuickSort(nums,index[<span class="number">1</span>]+<span class="number">1</span>,r);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">partition1</span><span class="params">(<span class="keyword">int</span> []nums ,<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> base = l;</span><br><span class="line">        <span class="comment">//双指针</span></span><br><span class="line">        <span class="keyword">int</span> lo = l, hi = r;</span><br><span class="line">        <span class="comment">//这种partition的实现细节有点不好理解</span></span><br><span class="line">        <span class="comment">//这种partition不能随机基准元素。。。。</span></span><br><span class="line">        <span class="comment">//参照了左神的代码发现其实可以在partition之前随机一个变量和lo交换，也有同样的效果也消除了输入的影响</span></span><br><span class="line">        <span class="keyword">while</span> (lo &lt; hi) &#123;</span><br><span class="line">            <span class="comment">//必须先从右往左,主要是为了归位的时候不出现问题</span></span><br><span class="line">            <span class="comment">//比如这里选取的基准元素是 lo 也就是子数组的第一个元素，如果先从左往右最后交换的就是lo和一个比lo大的数然而比lo大的数应该放在右边</span></span><br><span class="line">            <span class="comment">//反之如果选的是hi为基准就要先从左往右</span></span><br><span class="line">            <span class="comment">// 7  0  1  2    10  11  22</span></span><br><span class="line">            <span class="keyword">while</span> (nums[hi] &gt;= nums[base] &amp;&amp; lo &lt; hi) &#123;</span><br><span class="line">                hi--;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">while</span> (nums[lo] &lt;= nums[base] &amp;&amp; lo &lt; hi) &#123;</span><br><span class="line">                lo++;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (lo &lt; hi) &#123;</span><br><span class="line">                swap(nums, lo, hi);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//归位 lo==hi</span></span><br><span class="line">        swap(nums, hi, base);</span><br><span class="line">        <span class="keyword">return</span> lo;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//荷兰国旗优化的快排</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span>[] partition2(<span class="keyword">int</span> []arr ,<span class="keyword">int</span> l,<span class="keyword">int</span> r)&#123;</span><br><span class="line">        <span class="comment">// 7  0  1  2    10  11  22        </span></span><br><span class="line">        <span class="comment">//小于区为空</span></span><br><span class="line">        <span class="keyword">int</span> less=l-<span class="number">1</span>;</span><br><span class="line">        <span class="comment">//l ----&gt; more 为待定区</span></span><br><span class="line">        <span class="keyword">int</span> more=r;</span><br><span class="line">        <span class="keyword">while</span>(l&lt;more)&#123;</span><br><span class="line">            <span class="keyword">if</span>(arr[l]&lt;arr[r])&#123;</span><br><span class="line">                swap(arr,++less,l++);</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span>(arr[l]&gt;arr[r])&#123;</span><br><span class="line">                <span class="comment">//大于基准时 , 大于区扩大(大于区的前一个元素和当前元素交换，但是不知道大于区的前一个元素是什么情况，所以不能l++)</span></span><br><span class="line">                swap(arr,--more,l);</span><br><span class="line">            &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">                l++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//和大于区间的第一个交换 保证归位正确,如果选取的是以最左边为基准元素 这里就应该和less交换</span></span><br><span class="line">        <span class="comment">//到这里  [less+1,more-1]之间都是等于 基准元素 arr【r】 的</span></span><br><span class="line">        swap(arr,more,r);</span><br><span class="line">        <span class="comment">//到这  [less+1,more]之间都是等于 基准元素 arr【r】 的</span></span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;less+<span class="number">1</span>,more&#125;;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//************************************************************************</span></span><br><span class="line">    <span class="comment">//堆排序</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">HeapSort</span><span class="params">(<span class="keyword">int</span> []nums)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(nums.length&lt;<span class="number">2</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//构建大根堆</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>; i&lt;nums.length; i++) &#123;</span><br><span class="line">            heapInsert(nums,i);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//交换堆顶和最后一个节点</span></span><br><span class="line">        <span class="keyword">int</span> size= nums.length;</span><br><span class="line">        swap(nums,size-<span class="number">1</span>,<span class="number">0</span>);</span><br><span class="line">        size--;</span><br><span class="line">        <span class="keyword">while</span>(size&gt;<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="comment">//调整</span></span><br><span class="line">            heapIfy(nums,<span class="number">0</span>,size);</span><br><span class="line">            <span class="comment">//每次都和最后一个孩子节点交换，然后size--</span></span><br><span class="line">            swap(nums,--size,<span class="number">0</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//向上爬</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">heapInsert</span><span class="params">(<span class="keyword">int</span> []nums, <span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="comment">//迭代比较当前节点和父节点的值的大小</span></span><br><span class="line">        <span class="keyword">while</span>(nums[index]&gt;nums[(index-<span class="number">1</span>)/<span class="number">2</span>])&#123;</span><br><span class="line">            swap(nums,index,(index-<span class="number">1</span>)/<span class="number">2</span>);</span><br><span class="line">            index=(index-<span class="number">1</span>)/<span class="number">2</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//向下爬</span></span><br><span class="line">    <span class="comment">//index位置的值变小后继续调整为大根堆</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">heapIfy</span><span class="params">(<span class="keyword">int</span> []nums,<span class="keyword">int</span> index,<span class="keyword">int</span> size)</span></span>&#123;</span><br><span class="line">        <span class="comment">//左孩子</span></span><br><span class="line">        <span class="keyword">int</span> left=index*<span class="number">2</span>+<span class="number">1</span>;</span><br><span class="line">        <span class="comment">//节点有左孩子</span></span><br><span class="line">        <span class="keyword">while</span>(left&lt;size)&#123;</span><br><span class="line">            <span class="comment">//判断是否有右孩子.....</span></span><br><span class="line">            <span class="comment">//左右孩子里的最大值 有右孩子且右孩子大于左孩子</span></span><br><span class="line">            <span class="keyword">int</span> largest=left+<span class="number">1</span>&lt;size &amp;&amp; nums[left]&lt;nums[left+<span class="number">1</span>] ?left+<span class="number">1</span>:left;</span><br><span class="line">            largest=nums[largest]&gt;nums[index]?largest:index;</span><br><span class="line">            <span class="comment">//最大值等于自己</span></span><br><span class="line">            <span class="keyword">if</span>(largest==index)&#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//交换大孩子节点和自己</span></span><br><span class="line">            swap(nums,largest,index);</span><br><span class="line">            <span class="comment">//设置大孩子的index和左孩子</span></span><br><span class="line">            index=largest;</span><br><span class="line">            left=index*<span class="number">2</span>+<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//************************************************************************</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">swap</span><span class="params">(<span class="keyword">int</span> []nums,<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">        <span class="comment">//不知道为啥快排交换的时候这样写会出现很多0</span></span><br><span class="line">        <span class="comment">//查询知道，当a==b时自己和直接交换，a异或自己4次后a==0.....</span></span><br><span class="line">        nums[a]=nums[a]^nums[b];</span><br><span class="line">        nums[b]=nums[a]^nums[b];</span><br><span class="line">        nums[a]=nums[a]^nums[b];</span><br><span class="line">        <span class="comment">/*int temp=nums[a];</span></span><br><span class="line"><span class="comment">        nums[a]=nums[b];</span></span><br><span class="line"><span class="comment">        nums[b]=temp;*/</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// for test  对数器</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">comparator</span><span class="params">(<span class="keyword">int</span>[] arr)</span> </span>&#123;</span><br><span class="line">        Arrays.sort(arr);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// for test</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span>[] generateRandomArray(<span class="keyword">int</span> maxSize, <span class="keyword">int</span> maxValue) &#123;</span><br><span class="line">        <span class="keyword">int</span>[] arr = <span class="keyword">new</span> <span class="keyword">int</span>[(<span class="keyword">int</span>) ((maxSize + <span class="number">1</span>) * Math.random())];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">            arr[i] = (<span class="keyword">int</span>) ((maxValue + <span class="number">1</span>) * Math.random()) - (<span class="keyword">int</span>) (maxValue * Math.random());</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> arr;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// for test</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span>[] copyArray(<span class="keyword">int</span>[] arr) &#123;</span><br><span class="line">        <span class="keyword">if</span> (arr == <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">int</span>[] res = <span class="keyword">new</span> <span class="keyword">int</span>[arr.length];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">            res[i] = arr[i];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// for test</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Boolean <span class="title">isEqual</span><span class="params">(<span class="keyword">int</span>[] arr1, <span class="keyword">int</span>[] arr2)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> ((arr1 == <span class="keyword">null</span> &amp;&amp; arr2 != <span class="keyword">null</span>) || (arr1 != <span class="keyword">null</span> &amp;&amp; arr2 == <span class="keyword">null</span>)) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (arr1 == <span class="keyword">null</span> &amp;&amp; arr2 == <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (arr1.length != arr2.length) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; arr1.length; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (arr1[i] != arr2[i]) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// for test</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">printArray</span><span class="params">(<span class="keyword">int</span>[] arr)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (arr == <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">            System.out.print(arr[i] + <span class="string">&quot; &quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p>​        </p>

        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：常见的排序算法总结</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2018-12-11 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2018/12/11/83535e94/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2019/02/27/bef97aa3/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">LeetCode链表</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2018/12/03/3b46123d/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">NodeJS模仿Express封装路由</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2018/12/11/83535e94/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B8%B8%E8%A7%81%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93"><span class="nav-number">1.</span> <span class="nav-text">常见排序算法总结</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F"><span class="nav-number">1.1.</span> <span class="nav-text">冒泡排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F"><span class="nav-number">1.2.</span> <span class="nav-text">选择排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F"><span class="nav-number">1.3.</span> <span class="nav-text">直接插入排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F"><span class="nav-number">1.4.</span> <span class="nav-text">归并排序</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%9B%BE%E4%B8%8A%E9%9D%A2%E7%9A%84%E6%98%AF%E9%80%92%E5%BD%92%E7%89%88%E6%9C%AC%E7%9A%84%E5%BD%92%E5%B9%B6%EF%BC%8C%E5%AE%9E%E7%8E%B0%E5%A6%82%E4%B8%8B"><span class="nav-number">1.4.1.</span> <span class="nav-text">图上面的是递归版本的归并，实现如下</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%9D%9E%E9%80%92%E5%BD%92%E7%89%88%E6%9C%AC"><span class="nav-number">1.4.2.</span> <span class="nav-text">非递归版本</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%B8%89%E5%90%91%E5%88%87%E5%88%86%E7%9A%84%E5%BF%AB%E6%8E%92-%E8%8D%B7%E5%85%B0%E5%9B%BD%E6%97%97%E9%97%AE%E9%A2%98"><span class="nav-number">1.5.</span> <span class="nav-text">三向切分的快排(荷兰国旗问题)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A0%86%E6%8E%92%E5%BA%8F"><span class="nav-number">1.6.</span> <span class="nav-text">堆排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A0%86%E6%8E%92%E5%BA%8F%E6%9B%B4%E4%BC%98%E7%9A%84%E5%81%9A%E6%B3%95"><span class="nav-number">1.7.</span> <span class="nav-text">堆排序更优的做法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F"><span class="nav-number">1.8.</span> <span class="nav-text">希尔排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#BUG"><span class="nav-number">1.9.</span> <span class="nav-text">BUG</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AF%B9%E6%95%B0%E5%99%A8"><span class="nav-number">1.10.</span> <span class="nav-text">对数器</span></a></li></ol></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
